import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网.简单题.数字在升序数组中出现的次数
 */


public class Solution {
    public static int GetNumberOfK(int [] array , int k) {
        if(array.length == 0){
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        int count = 0;
        int mid = 0;
        while(left < right){
            mid = (left + right) / 2;
            if(array[mid] == k){
                break;
            }else if(array[mid] < k){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        for(int i = mid; i >= 0 && array[i] == k; i--){
            count++;
        }
        for(int j = mid + 1; j < array.length && array[j] == k; j++){
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3,3,3,3};
        int ret = GetNumberOfK(array,4);
    }
}
